1. Field of the Invention
The present invention relates to a scheduling method and scheduling apparatus for scheduling execution units processed in parallel in a multiprocessor system and also relates to a multiprocessor using such a method or apparatus.
2. Description of the Related Art
Operating systems released recently that support multitasks has installed therein a multithread technology that implements a multiprocessing environment in which it is possible to execute a plurality of processes concurrently and that allows each of processes to generate a plurality of threads inside the process for parallel processing. A process is assigned unique resources and an address space for its execution and cannot access areas assigned to other processes. In contrast, a thread is an execution unit generated inside a process. Threads can freely access each other's areas inside the process. A thread is a basic unit to which the operating system assigns execution time of a CPU.
Round-robin scheduling and priority scheduling are known as thread scheduling for assigning CPU time to threads. In round-robin scheduling, threads in a queue are sequentially selected at regular intervals for execution. In priority scheduling, threads are executed in the order of priority. In round-robin scheduling, CPU time is fairly assigned to threads in a queue at regular intervals so that the threads are executed. In priority scheduling, threads of respective priority levels are queued in queues provided for the respective priority levels. Threads are selected from queues in the descending order of priority so that the selected threads are executed.
In a multiprocessor system in which a plurality of processors are mounted, overall processing speed is increased by executing processes in parallel. When a multi-thread environment is implemented in a multiprocessor system, a thread is assigned to one of the processors for execution. Execution speed and memory consumption in a process vary depending on the order of execution of threads. In thread scheduling in a multiprocessor, consideration should be given to efficient ways of using processor resources and delivery and communication of data between threads. Therefore, ideas different from those adapted to thread scheduling in a single-processor system are required.